SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Graph embedding</title>

</head>

Graph embedding

</h1>

</header>

In <a href="Topological_graph_theory" title="Topological graph theory">topological graph theory</a>, an embedding (also spelled imbedding) of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> on a <a href="Surface_(mathematics)" title="Surface (mathematics)">surface</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> is a representation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> in which points of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> are associated with <a href="Graph_theory" title="Graph theory">vertices</a> and simple arcs (<a href="Homeomorphism" title="Homeomorphism">homeomorphic</a> images of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation>

</semantics>

</math><img src="./738f7d23bb2d9642bab520020873cccbef49768d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}" loading="lazy">) are associated with <a href="Graph_theory" title="Graph theory">edges</a> in such a way that:

<ul><li>the endpoints of the arc associated with an edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy"> are the points associated with the end vertices of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e,}</annotation>

</semantics>

</math><img src="./1cfc3e7aeae6ef256412eaa9f68d097804943b5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.73ex; height:2.009ex;" alt="{\displaystyle e,}" loading="lazy"></li>

<li>no arcs include points associated with other vertices,</li>

<li>two arcs never intersect at a point which is interior to either of the arcs.</li></ul>

Here a surface is a <a href="Connected_space" title="Connected space">connected</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">-<a href="Manifold" title="Manifold">manifold</a>.

Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{3}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{3}}</annotation>

</semantics>

</math><img src="./f936ddf584f8f3dd2a0ed08917001b7a404c10b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.732ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{3}}" loading="lazy">.<a href="#cite_note-3d-gd-1">[1]</a> A <a href="Planar_graph" title="Planar graph">planar graph</a> is one that can be embedded in 2-dimensional Euclidean space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{2}.}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{2}.}</annotation>

</semantics>

</math><img src="./066b155c535a38739cc0c4b288324cbb7a4a227a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.379ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{2}.}" loading="lazy">

Often, an embedding is regarded as an equivalence class (under homeomorphisms of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy">) of representations of the kind just described.

Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding".<a href="#cite_note-2">[2]</a>

This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "<a href="Graph_drawing" title="Graph drawing">graph drawing</a>" and "<a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">crossing number</a>".

<div class="mw-heading mw-heading2"><h2 id="Terminology">Terminology</h2></div>

If a graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> is embedded on a closed surface <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy">, the complement of the union of the points and arcs associated with

the vertices and edges of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> is a family of regions (or <a href="Face_(graph_theory)" class="mw-redirect" title="Face (graph theory)">faces</a>).<a href="#cite_note-gt01-3">[3]</a> A 2-cell embedding, cellular embedding or map is an embedding in which every face is homeomorphic to an open disk.<a href="#cite_note-4">[4]</a> A closed 2-cell embedding is an embedding in which the closure of every face is homeomorphic to a closed disk.

The genus of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> is the minimal integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> such that the graph can be embedded in a surface of <a href="Genus_(mathematics)" title="Genus (mathematics)">genus</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. In particular, a <a href="Planar_graph" title="Planar graph">planar graph</a> has genus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">, because it can be drawn on a sphere without self-crossing. A graph that can be embedded on a <a href="Torus" title="Torus">torus</a> is called a <a href="Toroidal_graph" title="Toroidal graph">toroidal graph</a>.

The non-orientable genus of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> is the minimal integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> such that the graph can be embedded in a non-orientable surface of (non-orientable) genus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.<a href="#cite_note-gt01-3">[3]</a>

The Euler genus of a graph is the minimal integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> such that the graph can be embedded in an orientable surface of (orientable) genus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/2}</annotation>

</semantics>

</math><img src="./95c3931a3fa03cc98cfacd2c49a7ca35b96eaa9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/2}" loading="lazy"> or in a non-orientable surface of (non-orientable) genus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. A graph is orientably simple if its Euler genus is smaller than its non-orientable genus.

The maximum genus of a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> is the maximal integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> such that the graph can be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">-cell embedded in an orientable surface of <a href="Genus_(mathematics)" title="Genus (mathematics)">genus</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Combinatorial_embedding">Combinatorial embedding</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Rotation_system" class="mw-redirect" title="Rotation system">Rotation system</a></div>

An embedded graph uniquely defines <a href="Cyclic_order" title="Cyclic order">cyclic orders</a> of edges incident to the same vertex. The set of all these cyclic orders is called a <a href="Rotation_system" class="mw-redirect" title="Rotation system">rotation system</a>. Embeddings with the same rotation system are considered to be equivalent and the corresponding equivalence class of embeddings is called combinatorial embedding (as opposed to the term topological embedding, which refers to the previous definition in terms of points and curves). Sometimes, the rotation system itself is called a "combinatorial embedding".<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a>

An embedded graph also defines natural cyclic orders of edges which constitutes the boundaries of the faces of the embedding. However handling these face-based orders is less straightforward, since in some cases some edges may be traversed twice along a face boundary. For example this is always the case for embeddings of trees, which have a single face. To overcome this combinatorial nuisance, one may consider that every edge is "split" lengthwise in two "half-edges", or "sides". Under this convention in all face boundary traversals each half-edge is traversed only once and the two half-edges of the same edge are always traversed in opposite directions.

Other equivalent representations for cellular embeddings include the <a href="Ribbon_graph" title="Ribbon graph">ribbon graph</a>, a topological space formed by gluing together topological disks for the vertices and edges of an embedded graph, and the <a href="Graph-encoded_map" title="Graph-encoded map">graph-encoded map</a>, an edge-colored <a href="Cubic_graph" title="Cubic graph">cubic graph</a> with four vertices for each edge of the embedded graph.

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

The problem of finding the graph genus is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> (the problem of determining whether an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-vertex graph has genus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>).<a href="#cite_note-8">[8]</a>

At the same time, the graph genus problem is <a href="Fixed-parameter_tractability" class="mw-redirect" title="Fixed-parameter tractability">fixed-parameter tractable</a>, i.e., <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

The first breakthrough in this respect happened in 1979, when algorithms of <a href="Time_complexity" title="Time complexity">time complexity</a>

O(nO(g)) were independently submitted to the Annual <a href="ACM_Symposium_on_Theory_of_Computing" class="mw-redirect" title="ACM Symposium on Theory of Computing">ACM Symposium on Theory of Computing</a>: one by I. Filotti and <a href="Gary_Miller_(computer_scientist)" title="Gary Miller (computer scientist)">G.L. Miller</a> and another one by <a href="John_Reif" title="John Reif">John Reif</a>. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.<a href="#cite_note-9">[9]</a> However, <a href="Wendy_Myrvold" title="Wendy Myrvold">Wendy Myrvold</a> and <a href="William_Lawrence_Kocay" title="William Lawrence Kocay">William Kocay</a> proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect.<a href="#cite_note-10">[10]</a>

In 1999 it was reported that the fixed-genus case can be solved in time <a href="Linear_time" class="mw-redirect" title="Linear time">linear</a> in the graph size and <a href="Double_exponential_function" title="Double exponential function">doubly exponential</a> in the genus.<a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Embeddings_of_graphs_into_higher-dimensional_spaces">Embeddings of graphs into higher-dimensional spaces</h2></div>

It is known that any finite graph can be embedded into a three-dimensional space.<a href="#cite_note-3d-gd-1">[1]</a>

One method for doing this is to place the points on any line in space and to draw the edges as curves each of which lies in a distinct <a href="Halfplane" class="mw-redirect" title="Halfplane">halfplane</a>, with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a <a href="Book_embedding" title="Book embedding">book embedding</a> of the graph. This <a href="Metaphor" title="Metaphor">metaphor</a> comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page"; the book thickness of the graph is the minimum number of halfplanes needed for such a drawing.

Alternatively, any finite graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in <a href="General_position" title="General position">general position</a> so that no four are coplanar. For instance, this may be achieved by placing the ith vertex at the point (i,i2,i3) of the <a href="Moment_curve" title="Moment curve">moment curve</a>.

An embedding of a graph into three-dimensional space in which no two of the cycles are topologically linked is called a <a href="Linkless_embedding" title="Linkless embedding">linkless embedding</a>. A graph has a linkless embedding if and only if it does not have one of the seven graphs of the <a href="Petersen_family" title="Petersen family">Petersen family</a> as a <a href="Minor_(graph_theory)" class="mw-redirect" title="Minor (graph theory)">minor</a>.

<div class="mw-heading mw-heading2"><h2 id="Gallery">Gallery</h2></div>

<div class="gallerytext">The <a href="Petersen_graph" title="Petersen graph">Petersen graph</a> and associated map embedded in the projective plane. Opposite points on the circle are identified yielding a closed surface of non-orientable genus 1.</div>

</li>

<div class="gallerytext">The <a href="Pappus_graph" title="Pappus graph">Pappus graph</a> and associated map embedded in the torus.</div>

</li>

<div class="gallerytext">The degree 7 <a href="Klein_graph" class="mw-redirect" title="Klein graph">Klein graph</a> and associated map embedded in an orientable surface of genus 3.</div>

</li>

</ul>

<ul><li><a href="Embedding" title="Embedding">Embedding</a>, for other kinds of embeddings</li>

<li><a href="Book_thickness" class="mw-redirect" title="Book thickness">Book thickness</a></li>

<li><a href="Graph_thickness" class="mw-redirect" title="Graph thickness">Graph thickness</a></li>

<li><a href="Doubly_connected_edge_list" title="Doubly connected edge list">Doubly connected edge list</a>, a data structure to represent a graph embedding in the <a href="Plane_(geometry)" class="mw-redirect" title="Plane (geometry)">plane</a></li>

<li><a href="Regular_map_(graph_theory)" title="Regular map (graph theory)">Regular map (graph theory)</a></li>

<li><a href="F%C3%A1ry's_theorem" title="Fáry's theorem">Fáry's theorem</a>, which says that a straight line planar embedding of a planar graph is always possible.</li>

<li><a href="Triangulation_(geometry)" title="Triangulation (geometry)">Triangulation (geometry)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCohenEadesLinRuskey1995" class="citation cs2">Cohen, Robert F.; <a href="Peter_Eades" title="Peter Eades">Eades, Peter</a>; Lin, Tao; <a href="Frank_Ruskey" title="Frank Ruskey">Ruskey, Frank</a> (1995), "Three-dimensional graph drawing", in <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a>; Tollis, Ioannis G. (eds.), Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, vol. 894, Springer, pp. 1–11, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-58950-3_351">10.1007/3-540-58950-3_351</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-58950-1</bdi></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKatohTanigawa2007" class="citation cs2">Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumerating Constrained Non-crossing Geometric Spanning Trees", Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, vol. 4598, Springer-Verlag, pp. 243–253, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.483.874">10.1.1.483.874</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-73545-8_25">10.1007/978-3-540-73545-8_25</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-73544-1</bdi></cite>.

</li>

<li id="cite_note-gt01-3">^ <a href="#cite_ref-gt01_3-0">a</a> <a href="#cite_ref-gt01_3-1">b</a> <cite id="CITEREFGrossTucker2001" class="citation cs2">Gross, Jonathan; <a href="Thomas_W._Tucker" title="Thomas W. Tucker">Tucker, Thomas W.</a> (2001), Topological Graph Theory, Dover Publications, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-41741-7</bdi></cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFLandoZvonkin2004" class="citation cs2">Lando, Sergei K.; Zvonkin, Alexander K. (2004), Graphs on Surfaces and their Applications, Springer-Verlag, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-00203-1</bdi></cite>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFMutzelWeiskircher2000" class="citation cs2"><a href="Petra_Mutzel" title="Petra Mutzel">Mutzel, Petra</a>; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs", Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1858, Springer-Verlag, pp. 95–104, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44968-X_10">10.1007/3-540-44968-X_10</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-67787-1</bdi></cite>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFDidjev1995" class="citation cs2">Didjev, Hristo N. (1995), "On drawing a graph convexly in the plane", <a href="International_Symposium_on_Graph_Drawing" title="International Symposium on Graph Drawing">Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings</a>, Lecture Notes in Computer Science, vol. 894, Springer-Verlag, pp. 76–83, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-58950-3_358">10.1007/3-540-58950-3_358</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-58950-1</bdi></cite>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFDuncanGoodrichKobourov2010" class="citation cs2">Duncan, Christian; <a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", <a href="International_Symposium_on_Graph_Drawing" title="International Symposium on Graph Drawing">Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers</a>, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 45–56, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0908.1608">0908.1608</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-11805-0_7">10.1007/978-3-642-11805-0_7</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-11804-3</bdi></cite>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFThomassen1989" class="citation cs2"><a href="Carsten_Thomassen_(mathematician)" title="Carsten Thomassen (mathematician)">Thomassen, Carsten</a> (1989), "The graph genus problem is NP-complete", Journal of Algorithms, 10 (4): 568–576, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2889%2990006-0">10.1016/0196-6774(89)90006-0</a></cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFFilottiMillerReif1979" class="citation cs2">Filotti, I. S.; <a href="Gary_Miller_(computer_scientist)" title="Gary Miller (computer scientist)">Miller, Gary L.</a>; <a href="John_Reif" title="John Reif">Reif, John</a> (1979), "On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proc. 11th Annu. ACM Symposium on Theory of Computing</a>, pp. 27–37, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800135.804395">10.1145/800135.804395</a></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFMyrvoldKocay2011" class="citation journal cs1"><a href="Wendy_Myrvold" title="Wendy Myrvold">Myrvold, Wendy</a>; <a href="William_Lawrence_Kocay" title="William Lawrence Kocay">Kocay, William</a> (March 1, 2011). "Errors in Graph Embedding Algorithms". Journal of Computer and System Sciences. 2 (77): 430–438. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2010.06.002">10.1016/j.jcss.2010.06.002</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFMohar1999" class="citation cs2"><a href="Bojan_Mohar" title="Bojan Mohar">Mohar, Bojan</a> (1999), "A linear time algorithm for embedding graphs in an arbitrary surface", <a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a>, 12 (1): 6–26, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.97.9588">10.1.1.97.9588</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS089548019529248X">10.1137/S089548019529248X</a></cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-10-12" href="https://en.wikipedia.org/wiki/?title=Graph_embedding&oldid=1250833565">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>